package exercises.leetcode.utils;

import exercises.newcoder.util.ListNode;
import exercises.newcoder.util.TreeNode;

import java.util.*;

/**
 * <a href="">
 * </a>
 *
 * <p><span color="#87CEEB">描述:</span>
 *
 * @author or2
 * @date 2021年09月28日 时间: 16:10
 */
public class Common {

    /**
     * 将字符串表示的<span color="red">满</span>二叉树 -> 跃然纸上
     *
     * @param str 测试用例中字符串形式的二叉树
     * @return 二叉树的头结点
     */
    public static TreeNode getTreeByStr(String str) {
        str = str.substring(1, str.length() - 1);
        String[] values = str.split(",");
        return createNode(0, values);
    }

    /**
     * 辅助上面的函数
     *
     * @param i      在字符串中的下标
     * @param values 字符串
     * @return 根节点
     */
    private static TreeNode createNode(int i, String[] values) {
        int length = values.length;
        if (i >= length)
            return null;

        if ("null".equals(values[i]))
            return null;
        TreeNode root = new TreeNode(Integer.parseInt(values[i]));
        root.left = createNode((i << 1) + 1, values);
        root.right = createNode(i + 1 << 1, values);

        return root;
    }

    /**
     * 将 leetcode 测试用例中字符串表示的二叉树 -> 跃然纸上
     *
     * @param str 测试用例中字符串形式的二叉树
     * @return 二叉树的头结点
     */
    public static TreeNode getTreeByStrForLeetcode(String str) {
        str = str.substring(1, str.length() - 1);
        ArrayList<String> stringList = new ArrayList<>(List.of(str.split(",")));
        /* 补成满二叉树 */
        for (int i = 0; i < stringList.size(); i++)
            if ("null".equals(stringList.get(i))) {
                /* 计算父节点 */
                int parent = (i << 1) + 1;
                if (parent < stringList.size()) {
                    stringList.add(parent, "null");
                    stringList.add(parent, "null");
                }
            }

        String[] values = stringList.toArray(String[]::new);
        return createNode(0, values);
    }

    public static List<List<String>> getArrayList2DimensionalFromString(String str) {
        str = str.substring(1, str.length() - 1);
        String[] layers = str.split("(?<=]),(?=\\[)");
        List<List<String>> res = new ArrayList<>(layers.length);

        for (int i = 0; i < layers.length; i++)
            res.add(getArrayLsitFromString(layers[i]));

        return res;
    }

    public static List<String> getArrayLsitFromString(String layer) {
        layer = layer.substring(1, layer.length() - 1);
        return Arrays.asList(layer.split(","));
    }

//———————————— leetcode - 单向链表 - 官方 ——————————————————————————————————————————————————————————————————————

    /**
     * Definition for singly-linked list.
     * <pre>{@code public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * } }</pre>
     */
    public static int[] stringToIntegerArray(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return new int[0];
        }

        String[] parts = input.split(",");
        int[] output = new int[parts.length];
        for (int index = 0; index < parts.length; index++) {
            String part = parts[index].trim();
            output[index] = Integer.parseInt(part);
        }
        return output;
    }

    public static ListNode stringToListNode(String input) {
        // Generate array from the input
        int[] nodeValues = stringToIntegerArray(input);

        // Now convert that list into linked list
        ListNode dummyRoot = new ListNode(0);
        ListNode ptr = dummyRoot;
        for (int item : nodeValues) {
            ptr.next = new ListNode(item);
            ptr = ptr.next;
        }
        return dummyRoot.next;
    }

    public static void prettyPrintLinkedList(ListNode node) {
        while (node != null && node.next != null) {
            System.out.print(node.val + "->");
            node = node.next;
        }

        if (node != null) {
            System.out.println(node.val);
        } else {
            System.out.println("Empty LinkedList");
        }
    }

//———————————— leetcode - 二叉树 - 官方 ——————————————————————————————————————————————————————————————————————

    /**
     * Definition for a binary tree node.
     * <pre>{@code public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }}</pre>
     */

    public static String treeNodeToString(TreeNode root) {
        if (root == null) {
            return "[]";
        }

        String output = "";
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();

            if (node == null) {
                output += "null, ";
                continue;
            }

            output += String.valueOf(node.val) + ", ";
            nodeQueue.add(node.left);
            nodeQueue.add(node.right);
        }
        return "[" + output.substring(0, output.length() - 2) + "]";
    }

    public static TreeNode stringToTreeNode(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return null;
        }

        String[] parts = input.split(",");
        String item = parts[0];
        TreeNode root = new TreeNode(Integer.parseInt(item));
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);

        int index = 1;
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int leftNumber = Integer.parseInt(item);
                node.left = new TreeNode(leftNumber);
                nodeQueue.add(node.left);
            }

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int rightNumber = Integer.parseInt(item);
                node.right = new TreeNode(rightNumber);
                nodeQueue.add(node.right);
            }
        }
        return root;
    }

    public static void prettyPrintTree(TreeNode node, String prefix, boolean isLeft) {
        if (node == null) {
            System.out.println("Empty tree");
            return;
        }

        if (node.right != null) {
            prettyPrintTree(node.right, prefix + (isLeft ? "│   " : "    "), false);
        }

        System.out.println(prefix + (isLeft ? "└── " : "┌── ") + node.val);

        if (node.left != null) {
            prettyPrintTree(node.left, prefix + (isLeft ? "    " : "│   "), true);
        }
    }

    public static void prettyPrintTree(TreeNode node) {
        prettyPrintTree(node, "", true);
    }
}
